/*
 * @lc app=leetcode.cn id=1049 lang=java
 *
 * [1049] 最后一块石头的重量 II
 */

// @lc code=start
class LastStoneWeightII {
  public int lastStoneWeightII(int[] stones) {
    int n = stones.length;
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += stones[i];
    }
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int i = 0; i < n; i++) {
      for (int j = target; j >= stones[i]; j--) {
        boolean no = dp[j];
        boolean yes = dp[j - stones[i]];
        dp[j] = no || yes;
      }
    }
    for (int i = target; i >= 0; i--) {
      if (dp[i]) {
        return sum - 2 * i;
      }
    }
    return sum;
  }
}
// @lc code=end
